package com.peng.leetcode.tree;

/**
 * SortedListToBST1
 * 109. 有序链表转换二叉搜索树
 * https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/
 * <p>
 * Created on 2022/12/5
 *
 * @author lupeng
 */
public class SortedListToBST1 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return dfs(head, null);
    }

    TreeNode dfs(ListNode head, ListNode tail) {
        if (head == tail) {
            return null;
        }
        ListNode middle = findMiddle(head, tail);
        TreeNode root = new TreeNode(middle.val);
        root.left = dfs(head, middle);
        root.right = dfs(middle.next, tail);
        return root;
    }



    ListNode findMiddle(ListNode l, ListNode r) {
        ListNode slow = l;
        ListNode fast = l.next;
        while (fast != r && fast.next != r) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}
